import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2024-11-11
 * Time:22:59
 */
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Test {
    public static void main(String[] args) {
        TestHeap testHeap=new TestHeap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        testHeap.initHeap(array);
        testHeap.createHeap();
        testHeap.heapSort();
        System.out.println();
    }
    public static void main3(String[] args) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(3);
        priorityQueue.offer(13);
    }
    //找出最小K个数
        public int[] smallestK(int[] arr, int k) {
            int[] ret=new int[k];
            if(arr==null||k<=0){
                return ret;
            }
            PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(arr.length);
            for (int i=0;i<arr.length;i++){
                priorityQueue.offer(arr[i]);
            }
            for (int i = 0; i < k; i++) {
                ret[i]=priorityQueue.poll();
            }
            return ret;
        }
    public static int[] maxLestK(int[] arr, int k) {
            int[] ret=new int[k];
            //判断是否合法
            if(arr==null || k<=0){
                return ret;
            }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        //先放K个元素
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //把剩下的元素与小根堆的堆顶元素进行比较，比他大则堆顶元素出队，大的元素入队
        for (int i = k; i < arr.length; i++) {
            int top=priorityQueue.peek();
            if(arr[i]>top){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        //遍历前K个元素放入数组中
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }

    public static void main2(String[] args) {
        int[] arr={10,4,2,6,15,24,9,0,4};
        int[] ret1=maxLestK(arr,3);
        System.out.println(Arrays.toString(ret1));
    }
    public static void main1(String[] args) {
        TestHeap testHeap=new TestHeap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        testHeap.initHeap(array);
        testHeap.createHeap();
        System.out.println("=====");
        testHeap.offer(90);
        System.out.println();
        int val=testHeap.poll();
        System.out.println(val);
    }

}
